package algorithms

import (
	"Algorithms/util"
)

func BF(main, model string) []int {
	res := []int{}
	if model == "" || main == "" || len(main) < len(model) {
		return res
	}
	b_main := []byte(main)
	b_model := []byte(model)

	for i := 0; i <= len(b_main)-len(b_model); i++ {
		for j := 0; j < len(b_model); j++ {
			if b_main[i+j] == b_model[j] {
				if j == len(b_model)-1 {
					res = append(res, i)
				}
			} else {
				break
			}
		}
	}
	return res
}

//利用hash值传递，可以避免一次次的计算整个长度为m的hash值，效率高于BF
func RK(main, model string) []int {
	res := []int{}
	mod := int(1e9 + 7)
	if model == "" || main == "" || len(main) < len(model) {
		return res
	}

	m := len(model)
	n := len(main)

	model_hash := StringHash(model, mod)
	//只用计算这一次
	main_hash := StringHash(main[0:m], mod)
	if main_hash == model_hash {
		res = append(res, 0)
	}

	am := modPow(26, m, mod)

	for i := 1; i <= n-m; i++ {
		//计算hash值，利用前一个结果可以简单计算，不需要调用StringHash函数
		main_hash = (main_hash*26 - am*int(main[i-1]-'a') + int(main[i+m-1]-'a')) % mod
		if main_hash < 0 {
			main_hash += mod
		}
		if main_hash == model_hash {
			res = append(res, i)
		}
	}
	return res
}

func modPow(x, n, mod int) int {
	res := 1
	for ; n > 0; n /= 2 {
		if n&1 == 1 {
			res = res * x % mod
		}
		x = x * x % mod
	}
	return res
}

func StringHash(b string, mod int) int {
	if len(b) > 10 {
		return -1
	}
	var res = 0

	for i := 0; i < len(b); i++ {
		res = (res*26 + int(b[i]-'a')) % mod
	}
	return res
}

//BM算法，利用坏字符串和好后缀匹配，返回第一个匹配的脚标
func BM(main, model string) []int {
	res := []int{}
	if model == "" || main == "" || len(main) < len(model) {
		return res
	}
	//生成好坏判别标准
	bc := generateBC(model)
	gc, prefix := generateGC(model)

	i := 0
	//从头遍历，到n-m为止
	for i <= len(main)-len(model) {
		//从后往前遍历坏字符
		j := len(model) - 1
		for ; j >= 0; j-- {
			if main[i+j] != model[j] {
				break
			}
		}
		if j < 0 {
			//匹配成功
			res = append(res, i)
			i += 1
			continue
		}
		//坏字符存在于主串，bc是坏字符在模式串里的位置xi，j是发现坏字符的位置也就是si
		x := j - bc[main[j+i]]
		var y int
		//好后缀判断,如果有好后缀的话
		if j < len(model)-1 {
			y = moveByGS(j, len(model), gc, prefix)
		}
		//移动两个判断条件里较大的那个
		max_move := util.Max(x, y)
		i += max_move
	}
	return res
}

var SIZE = 256

//返回坏字符在模式串中出现的位置数组，相同情况下选择靠后的
func generateBC(s string) []int {
	bc := make([]int, SIZE)
	//初始化bc
	for i := 0; i < SIZE; i++ {
		bc[i] = -1
	}
	for i := 0; i < len(s); i++ {
		bc[s[i]] = i
	}
	return bc
}

//返回好后缀在模式串中出现的位置数组，相同情况下选择靠后的
func generateGC(s string) (suffix []int, prefix []bool) {
	n := len(s)
	//用于存储后缀匹配的前面第一个出现的位置。index表示后缀长度 1~n-1
	suffix = make([]int, n)
	//用于存储是否匹配的是前缀的信息。index表示后缀长度 1~n-1
	prefix = make([]bool, n)
	//初始化
	for i := 0; i < n; i++ {
		suffix[i] = -1
		prefix[i] = false
	}
	//求共同后缀法，如果存在相同长度的后缀，后面那个会覆盖前面那个
	for i := 0; i < n-1; i++ {
		j := i
		//公共后缀长度
		k := 0
		//从后往前遍历
		for j >= 0 && s[j] == s[n-1-k] {
			//匹配到更长的一个了，所以长度+1，位置是j的位置
			k++
			suffix[k] = j
			j--
		}
		//说明是前缀，记录下来
		if j < 0 {
			prefix[k] = true
		}
	}
	return suffix, prefix
}

//j表示坏字符串在模式串的下标,n表示模式串长度
func moveByGS(j, n int, suffix []int, prefix []bool) int {
	//好后缀产长度
	k := n - j + 1
	//如果有匹配好后缀就直接移动这么多
	if suffix[k] != -1 {
		return j + 1 - suffix[k]
	}
	//没有好后缀匹配就判断子串里面有没有前缀
	for r := j + 2; r < n; r++ {
		//这里n-r是子串长度
		//本来不存在前缀就直接往后移n位就行
		//存在多长的k前缀，就变为n-k位了
		if prefix[n-r] {
			return r
		}
	}
	return n
}

//时间复杂度为：O(len(main+len(model)
//)
func KMP(main, model string) []int {
	res := []int{}
	if len(main) == 0 || len(model) == 0 {
		return res
	}
	//失效函数，index是前缀结尾字符下表，value是最长前缀字串结尾字符下标
	next := getNext(model)
	//模式串脚标
	j := 0
	for i := 0; i < len(main); i++ {
		for j > 0 && model[j] != main[i] {
			//往后跳几步，根据失效函数来确定
			j = next[j-1] + 1
		}
		//匹配了就继续
		if model[j] == main[i] {
			j++
		}
		if j == len(model) {
			res = append(res, i-len(model)+1)
			j = 0
		}
	}
	return res
}

//这里的next的算法采用动态规划法，时间复杂度为：O(len(model))
func getNext(model string) []int {
	next := make([]int, len(model))
	//不存在匹配项脚标设为-1
	next[0] = -1
	//作为动态规划的初始值
	k := -1
	for i := 1; i < len(model); i++ {
		//如果没有回到起点，或者[0:k+1]字串的k+1项和目前遍历到的i不匹配
		for k != -1 && model[k+1] != model[i] {
			//k需要回到[0:k]来寻找次长子串，比较次长子串的第k+1项能不能和i匹配
			k = next[k]
		}
		//如果能匹配就是k作为匹配前缀子串的最后一个index，如果不能，这个值就是0
		if model[k+1] == model[i] {
			k++
		}
		next[i] = k
	}
	return next
}
